{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "sys.path.append('../utils')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from aoc import * # get_input, d4, d8, d4n\n",
    "from itertools import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "YEAR = 2021\n",
    "DAY = 19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample = '''--- scanner 0 ---\n",
    "404,-588,-901\n",
    "528,-643,409\n",
    "-838,591,734\n",
    "390,-675,-793\n",
    "-537,-823,-458\n",
    "-485,-357,347\n",
    "-345,-311,381\n",
    "-661,-816,-575\n",
    "-876,649,763\n",
    "-618,-824,-621\n",
    "553,345,-567\n",
    "474,580,667\n",
    "-447,-329,318\n",
    "-584,868,-557\n",
    "544,-627,-890\n",
    "564,392,-477\n",
    "455,729,728\n",
    "-892,524,684\n",
    "-689,845,-530\n",
    "423,-701,434\n",
    "7,-33,-71\n",
    "630,319,-379\n",
    "443,580,662\n",
    "-789,900,-551\n",
    "459,-707,401\n",
    "\n",
    "--- scanner 1 ---\n",
    "686,422,578\n",
    "605,423,415\n",
    "515,917,-361\n",
    "-336,658,858\n",
    "95,138,22\n",
    "-476,619,847\n",
    "-340,-569,-846\n",
    "567,-361,727\n",
    "-460,603,-452\n",
    "669,-402,600\n",
    "729,430,532\n",
    "-500,-761,534\n",
    "-322,571,750\n",
    "-466,-666,-811\n",
    "-429,-592,574\n",
    "-355,545,-477\n",
    "703,-491,-529\n",
    "-328,-685,520\n",
    "413,935,-424\n",
    "-391,539,-444\n",
    "586,-435,557\n",
    "-364,-763,-893\n",
    "807,-499,-711\n",
    "755,-354,-619\n",
    "553,889,-390\n",
    "\n",
    "--- scanner 2 ---\n",
    "649,640,665\n",
    "682,-795,504\n",
    "-784,533,-524\n",
    "-644,584,-595\n",
    "-588,-843,648\n",
    "-30,6,44\n",
    "-674,560,763\n",
    "500,723,-460\n",
    "609,671,-379\n",
    "-555,-800,653\n",
    "-675,-892,-343\n",
    "697,-426,-610\n",
    "578,704,681\n",
    "493,664,-388\n",
    "-671,-858,530\n",
    "-667,343,800\n",
    "571,-461,-707\n",
    "-138,-166,112\n",
    "-889,563,-600\n",
    "646,-828,498\n",
    "640,759,510\n",
    "-630,509,768\n",
    "-681,-892,-333\n",
    "673,-379,-804\n",
    "-742,-814,-386\n",
    "577,-820,562\n",
    "\n",
    "--- scanner 3 ---\n",
    "-589,542,597\n",
    "605,-692,669\n",
    "-500,565,-823\n",
    "-660,373,557\n",
    "-458,-679,-417\n",
    "-488,449,543\n",
    "-626,468,-788\n",
    "338,-750,-386\n",
    "528,-832,-391\n",
    "562,-778,733\n",
    "-938,-730,414\n",
    "543,643,-506\n",
    "-524,371,-870\n",
    "407,773,750\n",
    "-104,29,83\n",
    "378,-903,-323\n",
    "-778,-728,485\n",
    "426,699,580\n",
    "-438,-605,-362\n",
    "-469,-447,-387\n",
    "509,732,623\n",
    "647,635,-688\n",
    "-868,-804,481\n",
    "614,-800,639\n",
    "595,780,-596\n",
    "\n",
    "--- scanner 4 ---\n",
    "727,592,562\n",
    "-293,-554,779\n",
    "441,611,-461\n",
    "-714,465,-776\n",
    "-743,427,-804\n",
    "-660,-479,-426\n",
    "832,-632,460\n",
    "927,-485,-438\n",
    "408,393,-506\n",
    "466,436,-512\n",
    "110,16,151\n",
    "-258,-428,682\n",
    "-393,719,612\n",
    "-211,-452,876\n",
    "808,-476,-593\n",
    "-575,615,604\n",
    "-485,667,467\n",
    "-680,325,-822\n",
    "-627,-443,-432\n",
    "872,-547,-609\n",
    "833,512,582\n",
    "807,604,487\n",
    "839,-516,451\n",
    "891,-625,532\n",
    "-652,-548,-490\n",
    "30,-46,-14'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "inp = get_input(YEAR, DAY)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def do_transform(inp):\n",
    "    return list(filter(lambda x: len(x) > 0, inp.split('\\n')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample = do_transform(sample)\n",
    "inp = do_transform(inp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(inp):\n",
    "    scanners = []\n",
    "    last = []\n",
    "    for line in inp:\n",
    "        if 'scanner' in line:\n",
    "            if len(last) > 0:\n",
    "                scanners.append(last)\n",
    "                last = []\n",
    "        else:\n",
    "            x, y, z = map(int, line.split(','))\n",
    "            last.append((x, y, z))\n",
    "    scanners.append(last)\n",
    "    n = len(scanners)\n",
    "    pos = [(0, 0, 0) for _ in range(n)]\n",
    "    \n",
    "    def overlapping(i, j):\n",
    "        s1 = set(scanners[i])\n",
    "        \n",
    "        for p in permutations(range(3)):\n",
    "            for c in product([-1, 1], [-1, 1], [-1, 1]):\n",
    "                t = [tuple(ci * x[pi] for pi, ci in zip(p, c)) for x in scanners[j]]\n",
    "                ni = len(scanners[i])\n",
    "                nj = len(scanners[j])\n",
    "                for x in scanners[i]:\n",
    "                    for y in t:\n",
    "                        delta = tuple(yi - xi for xi, yi in zip(x, y))\n",
    "                        t2 = [tuple(yi - di for yi, di in zip(y, delta)) for y in t]\n",
    "                        s2 = set(t2)\n",
    "                        ss = s1 & s2\n",
    "                        if len(ss) >= 12:                        \n",
    "                            scanners[j] = t2\n",
    "                            pos[j] = tuple(-x for x in delta)\n",
    "                            return True\n",
    "                    \n",
    "        return False\n",
    "    \n",
    "    last = 0\n",
    "    fixed = set([0])\n",
    "    free = set(range(1, n))\n",
    "    for _ in range(n - 1):\n",
    "        found = -1\n",
    "        \n",
    "        for i in free:\n",
    "            for j in fixed:\n",
    "                if overlapping(j, i):\n",
    "                    found = i\n",
    "                    break\n",
    "            if found != -1:\n",
    "                break\n",
    "        \n",
    "        fixed.add(found)\n",
    "        free.remove(found)\n",
    "        \n",
    "    beacons = set(scanners[0])\n",
    "    for i in range(1, n):\n",
    "        beacons = beacons | set(scanners[i])\n",
    "        \n",
    "    return len(beacons), max(sum(abs(x - y) for x, y in zip(a, b)) for a in pos for b in pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(79, 3621)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve(sample)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "ans = solve(inp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "submit_answer(ans[0], YEAR, DAY)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "submit_answer(ans[1], YEAR, DAY, level=2)"
   ]
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.12"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
